package first.forHuaWei.动态规划;

/**
 * @ClassName LC44
 * @description:
 * @author: 荣燊
 * @create: 2021-09-05 12:24
 **/
public class LC44 {
    // '?' 可以匹配任何单个字符。
    // '*' 可以匹配任意字符串（包括空字符串）


    // 通配符匹配，动态规划,主要是状态转移方程
    // dp[i][j] 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否能匹配
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length(); // p是特殊字符在的数组
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true; // 两字符串均未空，匹配成功
        // 先初始化,s为空，那么匹配字符串p必须为*号，前i个字符必须均为*号
        for (int i=1; i<=n; i++) {
            if (p.charAt(i-1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        // 开始判断
        for (int i=1; i<=m; i++) {
            for (int j=1; j<=n; j++) {
                // 如果匹配字符创为*
                if (p.charAt(j-1) == '*') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}
